package com.c2b.algorithm.leetcode.base;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/find-elements-in-a-contaminated-binary-tree/">在受污染的二叉树中查找元素(Find Elements in a Contaminated Binary Tree)</a>
 * <p>
 * 给出一个满足下述规则的二叉树：
 *     <ol>
 *         <li>root.val == 0</li>
 *         <li>如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1</li>
 *         <li>如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2</li>
 *     </ol>
 *     现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
 * </p>
 * <p>
 *     请你先还原二叉树，然后实现 FindElements 类：
 *     <ul>
 *         <li>FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。</li>
 *         <li>bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。</li>
 *     </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：
 *          ["FindElements","find","find"]
 *          [[[-1,null,-1]],[1],[2]]
 *      输出：
 *          [null,false,true]
 *      解释：
 *          FindElements findElements = new FindElements([-1,null,-1]);
 *          findElements.find(1); // return False
 *          findElements.find(2); // return True
 *
 * 示例 2：
 *      输入：
 *          ["FindElements","find","find","find"]
 *          [[[-1,-1,-1,-1,-1]],[1],[3],[5]]
 *      输出：
 *          [null,true,true,false]
 *      解释：
 *          FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
 *          findElements.find(1); // return True
 *          findElements.find(3); // return True
 *          findElements.find(5); // return False
 *
 * 示例 3：
 *      输入：
 *          ["FindElements","find","find","find","find"]
 *          [[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
 *      输出：
 *          [null,true,false,false,true]
 *      解释：
 *          FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
 *          findElements.find(2); // return True
 *          findElements.find(3); // return False
 *          findElements.find(4); // return False
 *          findElements.find(5); // return True
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>TreeNode.val == -1</li>
 *     <li>二叉树的高度不超过 20</li>
 *     <li>节点的总数在 [1, 10^4] 之间</li>
 *     <li>调用 find() 的总次数在 [1, 10^4] 之间</li>
 *     <li>0 <= target <= 10^6</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/23 11:52
 */
public class LC1261FindElementsInContaminatedBinaryTree_M {
    static class FindElements {

        private final Set<Integer> containValues;

        public FindElements(TreeNode root) {
            containValues = new HashSet<>();
            dfs(root, 0);
        }

        private void dfs(TreeNode currNode, int currNodeVal) {
            if (currNode == null) {
                return;
            }
            currNode.val = currNodeVal;
            containValues.add(currNodeVal);
            if (currNode.left != null) {
                dfs(currNode.left, currNodeVal * 2 + 1);
            }
            if (currNode.right != null) {
                dfs(currNode.right, currNodeVal * 2 + 2);
            }
        }

        public boolean find(int target) {
            return containValues.contains(target);
        }
    }

    static class FindElements2 {

        TreeNode rootNode;

        public FindElements2(TreeNode root) {
            this.rootNode = root;
        }

        /**
         * 题目中要求根节点的值为0。实际过程中，将根节点的值设为1，那么target也需要+1
         */
        public boolean find(int target) {
            if (target < 0) {
                return false;
            }
            /*
                对于一颗 由 1 为根节点，不断递增的树，用二进制表示为：
                                    1(0001)                              1
                                    /  \                               /  \
                                2(0010)3(0011)              ==>      10    11
                            / |         /   |                        / \   / \
                        4(0100)5(0101) 6(0110)7(0111)             100 101 110 111

                    左子节点的二进制表示为：父节点左移一位，后面跟上0
                    右子节点的二进制表示为：父节点左移一位，后面跟上1

                    所以：先找到目标树target的最高位的1,判断下一位是0还是1，
                        如果是0，则可能出现在左子树;
                        如果是1，则可能出现在右子树
            */
            TreeNode currNode = rootNode;
            target += 1;
            // 最高位的1开始计算
            // Integer.highestOneBit：获取到一个，最高位的1与target最高位的1位置相同，但左右两侧都为0的数。
            // 例如：target = 9 (0001 0001)  ==> highestBit1 = （0001 0000）
            // 例如：target =29 (0011 1001)  ==> highestBit1 = （0010 0000）
            int highestBit1 = Integer.highestOneBit(target);
            // 向左移动一位。用于判断：target最高位的1右侧一位1为是0还是1。
            int secondHighest1 = highestBit1 >> 1;
            while (secondHighest1 > 0 && currNode != null) {
                // 判断当前bit位是0还是1，如果是0，来到左子树；如果是1，来到右子树
                if ((target & secondHighest1) == 0) {
                    currNode = currNode.left;
                } else {
                    currNode = currNode.right;
                }
                // 继续判断下一位
                secondHighest1 >>= 1;
            }
            return currNode != null;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(-1);
        root1.right = new TreeNode(-1);
        //FindElements findElements1 = new FindElements(root1);
        //System.out.println(findElements1.find(1));
        //System.out.println(findElements1.find(2));

        TreeNode root2 = new TreeNode(-1);
        root2.left = new TreeNode(-1);
        root2.right = new TreeNode(-1);
        root2.left.left = new TreeNode(-1);
        root2.left.right = new TreeNode(-1);
        //FindElements findElements2 = new FindElements(root2);
        //System.out.println(findElements2.find(1));
        //System.out.println(findElements2.find(3));
        //System.out.println(findElements2.find(5));

        TreeNode root3 = new TreeNode(-1);
        root3.right = new TreeNode(-1);
        root3.right.left = new TreeNode(-1);
        root3.right.left.left = new TreeNode(-1);
        //FindElements findElements3 = new FindElements(root3);
        //System.out.println(findElements3.find(2));
        //System.out.println(findElements3.find(3));
        //System.out.println(findElements3.find(4));
        //System.out.println(findElements3.find(5));

        //FindElements2 findElements21 = new FindElements2(root1);
        //System.out.println(findElements21.find(1));
        //System.out.println(findElements21.find(2));
        //
        //FindElements2 findElements22 = new FindElements2(root2);
        //System.out.println(findElements22.find(1));
        //System.out.println(findElements22.find(3));
        //System.out.println(findElements22.find(5));

        FindElements2 findElements23 = new FindElements2(root3);
        //System.out.println(findElements23.find(2));
        //System.out.println(findElements23.find(3));
        //System.out.println(findElements23.find(4));
        //System.out.println(findElements23.find(5));
        System.out.println(findElements23.find(28));
    }
}
